package array.sliding_window;

public class lc76 {
    public static void main(String[] args) {
        String s="ADOBECODEBANC";
        String t="ABC";
        System.out.println(minWindow(s, t));

    }
    public static String minWindow(String s, String t) {
        if(t.length()>s.length()){
            return "";
        }else if(t.length()==s.length()){
            if(s.equals(t))
                return s;
            return "";
        }else{
            char[] sstr=s.toCharArray();
            char[] tstr=t.toCharArray();
            int left=0;
            int right=0;
            int cur_length=0;
            int min_length=0;
            int min_left=0;
            int min_right=0;
            while(right<sstr.length){
                cur_length=right-left+1;
                while(contain(sstr,tstr,left,right)){//左闭右闭区间
                    if(cur_length<min_left||min_length==0){
                        cur_length=right-left+1;
                        min_length=cur_length;
                        min_left=left;
                        min_right=right;
                    }
                    left++;
                }
                right++;
            }
            return s.substring(left,right);
        }
        //return "";

    }
    public static boolean contain(char[] sstr,char[] tstr,int left,int right){
        if(tstr.length>sstr.length){
            return false;
        }else if(tstr.length==sstr.length){
            for(int i=0;i<sstr.length;++i){
                if(sstr[i]!=tstr[i]){
                    return false;
                }
            }
            return true;
        }else{
            int j=left;
            boolean[] t=new boolean[tstr.length];
            for(j=left;j<=right;j++){
                for(int k=0;k<tstr.length;k++){
                    if(sstr[j]==tstr[k]){
                        t[k]=true;
                        break;
                    }
                }
            }
            for (int i = 0; i <t.length ; i++) {
                if(t[i]=false)
                    return false;
            }
            return true;

        }
    }
}
